import functools
class Solution(object):
    def minScoreTriangulation(self, values):
        n = len(values)
        @functools.cache
        def search(i, j):
            if j - i == 2:
                return values[i] * values[i + 1] * values[j]
            if j - i < 2:
                return 0
            min_val = float('inf')
            for k in range(i + 1, j):
                now_trangle = values[i] * values[k] * values[j] + search(i, k) + search(k, j)
                min_val = min(now_trangle, min_val)
            return min_val

        return search(0, n - 1)





data = Solution()
values = [1, 3, 1, 4, 1, 5]
print(data.minScoreTriangulation(values))
